package datastructure.tree;

class ThNode {
    char data;
    ThNode lchild, rchild;
    int ltag, rtag;

    public ThNode() {
        lchild = rchild = null;
        ltag = rtag = 0;
    }

    public ThNode(char data) {
        this();
        this.data = data;
    }
}

public class BiThrTree {
    ThNode b;//二叉树的根节点
    ThNode root;//线索二叉树的头结点
    ThNode pre;//用于中序线索化，指向中序前驱节点
    String bstr;

    public BiThrTree() {
        root = null;
    }

    public void CreateBiThrTree() {
        root = new ThNode();
        root.ltag = 0;
        root.rtag = 1;
        if (b == null) {
            root.lchild = root;
            root.rchild = null;
        } else {
            root.lchild = b;
            pre = root;
            Thread(b);
            pre.rchild = root;
            pre.rtag = 1;
            root.rchild = pre;
        }
    }

    private void Thread(ThNode p) {
        if (p != null) {
            Thread(p.lchild);
            if (p.lchild == null) {
                p.lchild = pre;
                p.ltag = 1;
            } else p.ltag = 0;

            if (pre.rchild == null) {
                pre.rchild = p;
                pre.rtag = 1;
            } else pre.rtag = 0;
            pre = p;
            Thread(p.rchild);
        }
    }

    /*
        通过线索中序遍历
     */
    public void ThInOrder() {
        ThNode p = root.lchild;
        while (p != root) {
            while (p != root && p.ltag == 0) p = p.lchild; //找左孩子ltag=1的节点
            System.out.print(p.data);
            while (p.rtag == 1 && p.rchild != root) {
                p = p.rchild;
                System.out.print(p.data);
            }
            p = p.rchild;
        }
    }
}
